High bandwidth and Quality of Service (QoS) requirements of continuous (multimedia) data such as audio and video pose numerous performance related challenges. The stringent QoS requirements of most audio/video applications require on-time delivery of pieces of data from the source (the disc where the media is stored) all the way to the destination (the client where it is played back). Missing the delivery deadlines may result in user-noticeable degradation of the playback quality, called glitches.
Disc scheduling algorithms can be classified into three groups: (1) algorithms that are designed for general purpose disc access (mostly for discrete data access), (2) algorithms for continuous data (e.g., video/audio streams), and (3) algorithms for mixed-media workloads.
The First Come First Served (FCFS) disc scheduling. algorithm accepts requests one at a time and serves them in order. This is an easy to implement and intrinsically fair algorithm. However, numerous studies have shown that FCFS often results in suboptimal performance due to high average seek and rotation time.
The Shortest Seek Time First (SSTF) algorithm chooses among all requests the one with the minimum seek time from the current head position. This algorithm minimizes seek time. However, this comes at the expense of high response time variance and the starvation of some requests. Requests to the middle of the disc will get immediate service at the expense of requests to the innermost/outermost disc areas.
The SCAN scheduling algorithm, like SSTF, orders requests to minimize seek time. However, unlike SSTF, it also takes the direction of the current disc movement into account. It serves the requests in an elevator-like manner, moving the disc head back and forth across all the cylinders and servicing the requests along the path. It allows seek time optimizations while reducing the response time variance. disc head back and forth across all the cylinders and servicing the requests along the path. It allows seek-time optimizations while reducing the response time variance.
C-SCAN (Cyclical SCAN), a variation of SCAN, always moves the head in one direction. When the head reaches the last cylinder, it returns to the first cylinder without servicing any request along the way. C-SCAN treats each cylinder equally rather than favoring the center cylinders as SCAN does. Although it offers fairer service with more uniform waiting times, its performance is somewhat worse than SCAN.
The LOOK algorithm is another SCAN variation that changes the scanning direction if there is no pending requests to be served in the current direction of travel. C-SCAN and LOOK can be combined resulting in the C-LOOK algorithm.
VSCAN(R) algorithm operates as SSTF except that every time it changes direction it adds a penalty based on the parameter R and the seek distance. When R=1 it reduces to SCAN and when R=0 it reduces to SSTF. Past work suggests that VSCAN(0.2) provides a good balance between average response time and starvation resistance.
The Group Sweeping Scheduling (GSS) algorithm provides a compromise by grouping streams and employing round-robin scheduling for the different groups and SCAN scheduling for the stream's block in a group.
The Continuous Media File System defines several disc scheduling algorithms in terms of slack time, the amount of time the scheduler has before it has to schedule a real-time request. Compressing out slack time is analogous to allowing reordering before a request's deadline.
In the field of disc scheduling Shortest Positioning Time First (SPTF) is the current state-of-the-art algorithm for overall disc scheduling that takes advantage of position based knowledge including seek and rotational latency. However, it does not take advantage of the information from the application. It only optimizes based on the current state of the disc head.
In the field of real-time scheduling, the most widely used scheduling algorithm is Earliest Deadline First (EDF). This algorithm takes advantage of application information, specifically the deadlines by which the requests must be serviced. This algorithm orders all the requests based on their deadlines and schedules the requests with the earliest deadline first. In a disc setting, it suffers from poor resource utilization and overall performance because it does not attempt to reduce the overhead of seek and rotational latency.
SCAN-EDF is a variant of a disc scheduling algorithm which combines EDF and SCAN. Just like EDF, SCAN-EDF services the requests with the earliest deadlines first. If several requests have the same (or approximate) deadline, then SCAN is used to schedule these requests. As a result, the effectiveness of SCAN-EDF algorithm is dependent on how many requests have the same deadline. Variations of this algorithm for combined discrete and continuous (multimedia) workloads have been proposed.
Additional scheduling algorithms have adopted the notion of scheduling in rounds. Each continuous media is divided into multiple fragments. The current fragments for all the active streams are scheduled in a given round. A previous patent proposed the use of a common retrieval period for a similar purpose. All of this previous work is based on application level information for determining the size of the rounds without regard to detailed disc level information.
Scheduling algorithms are optimized by either the application view of the system or the disc view of the system, considered independently. On one hand, scheduling algorithms such as SPTF are purely optimized for disc performance (i.e., minimum response time) but do not meet needs of the real-time applications. On the other hand, scheduling algorithms such as EDF are purely optimized for real-time applications but severely lack disc optimizations.
Not all applications require the same performance and QoS. Storage devices can take advantage of this diversity to keep all the applications satisfied. This type of optimization is not possible today because storage devices see and treat all the data the same and there is no interface defined to specify requirements of each application. Instead, optimization decisions are made by the application (the multimedia server in our case). However, applications lack some of the critical information such as the position of the read/write head on the disc or location of remapped blocks.
There is a need for a scheduling method that takes into account both application considerations and disc considerations.